package cn.lbd.arithmetic.leetcode.editor.cn;
//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 示例： 
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
// 
// Related Topics 链表 数学 
// 👍 4816 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
/*class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}*/

class Solution2 {

    /**
     * 将当前结点初始化为返回列表的哑结点。
     * 将进位 carry 初始化为 0。
     * 将 p 和 q 分别初始化为列表 l1 和 l2 的头部。
     * 遍历列表 l1 和 l2 直至到达它们的尾端。
     * 将 x 设为结点 p 的值。如果 p 已经到达 l1 的末尾，则将其值设置为 0。
     * 将 y 设为结点 q 的值。如果 q 已经到达 l2 的末尾，则将其值设置为 0。
     * 设定 sum = x + y + carry
     * 更新进位的值，carry = sum / 10
     * 创建一个数值为 (sum mod 10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
     * 同时，将 p 和 q 前进到下一个结点。
     * 检查 carry = 1 是否成立，如果成立，则向返回列表追加一个含有数字 1 的新结点。
     * 返回哑结点的下一个结点。
     * **/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //结果链表的头节点
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        //进位
        int carry = 0;
        while (p != null || q != null) {
            //遍历链表，如果到达链表末尾，将其值置为0
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            //每位上的结果都 ==> 节点值的和 + 进位 （/10：取进位  %10：取个位）
            int sum = carry + x + y;
            carry = sum / 10;
            //如果sum >= 10，保留个位，携带进位位进入下一位
            curr.next = new ListNode(sum % 10);
            //更新三个链表的指针
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        //如果到了最高位还有进位，就直接向更高位补上carry
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummyHead.next;
    }

    //不带头结点的算法
    /*public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1.next == null || l2.next == null) {
            System.out.println("链表为空");
            return null;
        }
        ListNode p1 = l1, p2 = l2;
        ListNode results = new ListNode(0);
        ListNode result = results;
        //进位,一个位数上最大为 9+9+1 = 19，carry = 0 | 1
        int carry = 0;
        while (true) {
            if (p1.next == null || p2.next == null) {
                break;
            }
            int tempResult = 0;
            tempResult = p1.val + p2.val + carry;
            if (tempResult >= 10) {
                tempResult %= 10;
                carry += 1;
            }
            ListNode listNode = new ListNode(tempResult);
            listNode.next = result.next;
            result.next =listNode;
            if (carry > 0) {
                ListNode listNode1 = new ListNode(p1.next.val + p2.next.val + carry);
                listNode1.next = result.next.next;
                result.next.next = listNode1;
                carry -= 1;
            }
            p1 = p1.next;
            p2 = p2.next;
            result = result.next;
        }
        return results.next;
    }*/

    //带头结点的算法
    /*public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1.next == null || l2.next == null) {
            System.out.println("链表为空");
            return null;
        }
        ListNode p1 = l1, p2 = l2;
        ListNode results = new ListNode(0);
        ListNode result = results;
        int carry = 0;
        while (true) {
            if (p1.next.next == null || p2.next.next == null) {
                break;
            }
            int tempResult = 0;
            tempResult = p1.next.val + p2.next.val + carry;
            if (tempResult >= 10) {
                tempResult %= 10;
                carry += 1;
            }
            ListNode listNode = new ListNode(tempResult);
            listNode.next = result.next;
            result.next =listNode;
            if (carry > 0) {
                ListNode listNode1 = new ListNode(p1.next.next.val + p2.next.next.val + carry);
                listNode1.next = result.next.next;
                result.next.next = listNode1;
                carry -= 1;
            }
            p1 = p1.next;
            p2 = p2.next;
            result = result.next;
        }
        return results;
    }*/

    /*//带头结点的测试代码
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(3);
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.add(listNode1);
        singleLinkedList1.add(listNode2);
        singleLinkedList1.add(listNode3);
        SingleLinkedList.reserve(singleLinkedList1.getHead());
        singleLinkedList1.list();

        System.out.println("===========================================");

        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(6);
        ListNode listNode6 = new ListNode(4);
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.add(listNode4);
        singleLinkedList2.add(listNode5);
        singleLinkedList2.add(listNode6);
        SingleLinkedList.reserve(singleLinkedList2.getHead());
        singleLinkedList2.list();

        System.out.println("===========================================");

        //7->0->8
        ListNode listNode = addTwoNumbers(singleLinkedList1.getHead(), singleLinkedList2.getHead());
        if (listNode.next == null) {
            System.out.println("链表为空");
            return;
        }
        ListNode temp = listNode.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }*/
}

//不带头结点的测试类
/*class MainClass {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for(int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static ListNode stringToListNode(String input) {
        // Generate array from the input
        int[] nodeValues = stringToIntegerArray(input);

        // Now convert that list into linked list
        ListNode dummyRoot = new ListNode(0);
        ListNode ptr = dummyRoot;
        for(int item : nodeValues) {
            ptr.next = new ListNode(item);
            ptr = ptr.next;
        }
        return dummyRoot.next;
    }

    public static String listNodeToString(ListNode node) {
        if (node == null) {
            return "[]";
        }

        String result = "";
        while (node != null) {
            result += Integer.toString(node.val) + ", ";
            node = node.next;
        }
        return "[" + result.substring(0, result.length() - 2) + "]";
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            ListNode l1 = stringToListNode(line);
            line = in.readLine();
            ListNode l2 = stringToListNode(line);

            ListNode ret = new Solution().addTwoNumbers(l1, l2);

            String out = listNodeToString(ret);

            System.out.print(out);
        }
    }
}*/

//管理链表的类（带头结点）
/*class SingleLinkedList {

    //头节点
    private ListNode head = new ListNode(0);

    public ListNode getHead() {
        return head;
    }

    //添加节点到单向链表尾部
    public void add(ListNode heroNode) {
        ListNode temp = head;
        while (true) {
            //找到链表的最后一个节点
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    //根据排名将英雄按序插入
    public void addByOrder(ListNode heroNode) {
        ListNode temp = head;
        boolean flag = false; //是否有重复编号
        while (true) {
            //遍历到尾部
            if (temp.next == null) {
                break;
            }
            if (temp.next.val > heroNode.val) {
                //找到待插入位置
                break;
            } else if (temp.next.val == heroNode.val) {
                //编号重复
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //插入节点
        if (flag) {
            //有重复编号
            System.out.println("插入编号" + heroNode.val + "已存在");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息，根据编号no来修改，即No编号不能改
        *//*public void update(HeroNode heroNode) {
            if (head.next == null){
                System.out.println("链表为空");
                return;
            }
            HeroNode temp = head.next;
            boolean flag = false;//标记是否找到元素

            while(true){
                if (temp.next == null){
                    break;
                }

                if (temp.no == heroNode.no){
                    flag = true;
                    break;
                }
                temp = temp.next;

            }

            if (flag){
                temp.name = heroNode.name;
                temp.nickName = heroNode.nickName;
            }else {
                System.out.println("未找到"+heroNode.no+"号英雄");
            }
        }*//*


    //删除节点
    public void del(int no) {
        //遍历到链表尾部
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        ListNode temp = head;
        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.val == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("未找到" + no + "号英雄");
        }
    }

    //显示链表
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        ListNode temp = head.next;

        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }

    //逆转单链表
    public static void reserve(ListNode head) {
        //如果链表长度为0或1，则不需要逆转
        if (head.next == null && head.next.next == null) {
            return;
        }
        //head链表的辅助指针
        ListNode temp = head.next;
        //逆转后的头节点
        ListNode reserveHead = new ListNode(0);
        //存储原链表临时的下一节点数据
        ListNode next = null;
        while (temp != null) {//最后一个节点也移入了新链表
            next = temp.next;
            //加入到新链表最前端
            temp.next = reserveHead.next;
            reserveHead.next = temp;
            //temp = temp.next
            temp = next;
        }
        //将旧链表头节点指向新链表的第一个节点
        head.next = reserveHead.next;
    }


}*/


//leetcode submit region end(Prohibit modification and deletion)
